Leonid Genrikhovich Khachiyan
He was most famous for his Ellipsoid method (1979) for linear programming,
Early life and education
Khachiyan was born on May 3, 1952, in
Leningrad to Armenian parents Genrikh Borisovich Khachiyan, a mathematician and professor of theoretical mechanics, and Zhanna Saakovna Khachiyan, a
civil engineer.
His grandparents were
Karabakh Armenians.
He had two brothers: Boris and Yevgeniy (Eugene).
His family moved to
Moscow in 1961, when he was nine.
He received a master's degree from the Moscow Institute of Physics and Technology.
In 1978 he earned his Ph.D. in computational mathematics/theoretical mathematics from the Computer Center of the Soviet Academy of Sciences and in 1984 a D.Sc. in
computer science from the same institution.
Career
Khachiyan began his career at the Soviet Academy of Sciences,
working as a researcher at the academy's Computer Center in Moscow.
He also worked as an adjunct professor at the Moscow Institute of Physics and Technology.
In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems."
Khachiyan immigrated to the United States in 1989.
He first taught at Cornell University as a visiting professor. In 1990 he joined Rutgers University as a visiting professor.
He became
tenure of
computer science at Rutgers in 1992.
By 2005, he held the position of Professor II at Rutgers, reserved for those faculty who have achieved scholarly eminence in their discipline.
Work on linear programming
Ellipsoid method
Khachiyan is best known for his four-page February 1979 paper
[Khachiyan, L. G. 1979. "A Polynomial Algorithm in Linear Programming". Doklady Akademii Nauk SSSR 244, 1093-1096 (translated in Soviet Mathematics Doklady 20, 191-194, 1979).] that indicated how an
ellipsoid method for linear programming can be implemented in polynomial time.
The paper was translated into several languages and spread around the world unusually quickly. Authors of a 1981 survey of his work noted that it "has caused great excitement and stimulated a flood of technical papers" and was covered by major newspapers.
It was originally published without proofs, which were provided by Khachiyan in a later paper published in 1980
[Khachiyan, L. G. 1980. "Polynomial Algorithms in Linear Programming". Zhurnal Vychisditel'noi Matematiki i Matematicheskoi Fiziki (USSR Computational Mathematics and Mathematical Physics) 20, 51-68.] and by Peter Gács and Laszlo Lovász in 1981.
It was Gács and Lovász who first brought attention to Khachiyan's paper at the International Symposium on Mathematical Programming in Montreal in August 1979.
It was further popularized when
Gina Kolata reported it in
Science Magazine on November 2, 1979.
Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."
Personal life and death
Khachiyan spoke Russian and English, but not Armenian.
Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."
A 1979
New York Times profile of him described Khachiyan as "a relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school."
He was known as "Leo"
Khachiyan married Olga Pischikova Reynberg, of Russian-Jewish origin,
Recognition
In 1982 he was awarded the prestigious
Fulkerson Prize by the Mathematical Programming Society and the American Mathematical Society
for outstanding papers in the area of discrete mathematics,
particularly his 1979 article "A polynomial algorithm in linear programming."
Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems."
- Notes
- Citations
External links
